package 题目集.倍增算法.st表;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

/**
 * https://www.luogu.com.cn/problem/P1890
 * 给定 n个正整数
 * m次询问，每次询问l,r区间内的最大公约数
 */
public class ch03_区间最大公约数 {
    static int maxN = (int) (1e4 + 10), maxM = (int) 1e6 + 10;
    static int maxP = (int) Math.ceil(Math.log(maxN) / Math.log(2)) - 1;
    static int[][] st = new int[maxN][maxP + 1];
    static int n, m, power;

    public static void main(String[] args) {
        Reader sc = new Reader();
        n = sc.nextInt();
        m = sc.nextInt();
        power = (int) Math.ceil(Math.log(n) / Math.log(2)) - 1;
        for (int i = 1; i <= n; i++) {
            st[i][0] = sc.nextInt();
        }
        build();
        while (m-- > 0) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            if (l==r) {
                System.out.println(st[l][0]);
                continue;
            }
            int len = r - l + 1;
            int p = (int) Math.ceil(Math.log(len) / Math.log(2)) - 1;
            //r - (1 << p) + 1，额外+1是因为r是终点，而r-(1<<p)不包含r
            int gcd = gcd(st[l][p], st[r - (1 << p) + 1][p]);
            System.out.println(gcd);
        }
    }

    private static void build() {
        for (int p = 1; p <= power; p++) {
            int offs = 1 << p - 1;
            for (int i = 1; i <= n; i++) {
                st[i][p] = gcd(st[i][p - 1], st[i+offs][p-1]);
            }
        }
    }

    public static int gcd(int a, int b) {
        int temp;
        while (b != 0) {
            a %= b;
            temp = a;
            a = b;
            b = temp;
        }
        return a;
    }


    static class Reader {
        static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

        public Reader(Object... o) {
        }

        public int nextInt() {
            try {
                in.nextToken();
            } catch (Exception ignored) {
            }
            return (int) in.nval;
        }
    }
}
